(Density Based Spatial Clustering of Applications with Noise)
Clustering basado en densidad (1996)
Objetivo: Encontrar grupos de instancias tales que las instancias en un cluster sean similares entre sí, y diferentes de las instancias en otros clusters, donde se Minimiza la distancia Intra-Cluster y Maximiza la distancia Inter-Cluster. Para esto, la mejor definición de cluster depende de la naturaleza de los datos y los resultados deseados.
¿En qué consiste?
Tiene un enfoque basado en la densidad, modelando los clusters como cúmulos de alta densidad de puntos. Por lo cual, si un punto pertenece a un clúster, debe estar cerca de un montón de otros puntos de dicho clúster. Se basa en el concepto de densidad de un punto, que mide el número de puntos que son alcanzables desde él considerando un determinado radio.
Un cluster en una región densa de puntos, separada por regiones poco densas de otras regiones densas.
¿Cómo funciona?
Se definen dos parámetros, un número épsilon (Eps) positivo y un número natural minPoints (MinPts), y se elige un punto arbitrario x en el conjunto de datos. Si x es un punto central (core points), se empieza a construir un cluster alrededor de él, tratando de descubrir componentes denso-conectadas. A continuación se elige un nuevo punto arbitrario (y) y se repite el proceso el cual termina cuando no se pueden añadir nuevos puntos a ningún clúster.
Vecindad de un punto x: esfera centrada en x y radio Eps
Densidad de un punto x: cantidad de puntos dentro de la vecindad de x.
Puntos centrales (core points) son aquellos tales que en su vecindad de radio Eps, hay una cantidad de puntos mayor o igual que un umbral MinPts especificado. Son los puntos interiores de un cluster.
Un punto borde o frontera tiene menos puntos que MinPts en su vecindad, pero pertenece a la vecindad de un punto central.
Un punto ruido (noise) es aquel que no es ni central ni borde.
En consecuencia, los puntos centrales están en regiones de alta densidad, los puntos borde en la frontera de regiones densas y los puntos ruido en regiones de baja densidad. Este algoritmo busca clusters comprobando la vecindad de cada punto de la base de datos y va añadiendo puntos que son denso-alcanzables desde un punto central.
Un punto q es directamente denso-alcanzable desde otro punto t (con relación a los parámetros MinPts y Eps) si t es un punto central y q pertenece a la vecindad de t. Un punto q es denso-alcanzable desde un punto t si existe una cadena de puntos \(t_0\), \(t_1\),… \(t_m\), tales que \(t_{i-1}\) es directamente denso-alcanzable desde \(t_i\), 1 ≤ i ≤ m, \(t_0\) = q y \(t_m\) = t.
En los puntos de un mismo cluster, su k-ésimo vecino debería estar más o menos a la misma distancia. En los puntos de ruido, su k-ésimo vecino debería estar más lejos.
Datos originales vs Cluster DBSCAN:
En esta imagen podemos ver cómo quedaría un agrupamiento luego de utilizar DBSCAN.
K-Means vs DBSCAN:
Con K-Means vemos que los clusters quedan formados por puntos de ambas curvas, mientras que con DBSCAN se pueden separar fácilmente ambas regiones en grupos distintos.
Fuente: http://www.datainterfaces.org/projects/flickr/#torino
(La descarga de los datos se realizó haciendo uso de técncias básicas de web scraping)
¿Qué es Flickr?
Flickr es una plataforma digital, propiedad de Yahoo, que permite guardar, buscar y compartir fotografías y videos en Internet. Servicios similares incluyen a plataformas como Instagrama o Pinterest.
En un esfuerzo por abrir sus datos al público Flickr, en conjunto con YahooLabs, crearon el Flickr cities. El proyecto consiste el desarrollo de una interface exploratoria de millones de imágenes que se han compartido mediante la plataforma en distintas ciudades, que se mapean en una interface visual (un mapa). Dentro de los metadatos de cada fotografía podemos encontrar el lugar, la fecha, el tema, la nacionalidad del usuario y la hora.
Lo anterior nos permite contar con información valiosa de los patrones y hábitos que desarrollan los turistas de cierta nacionalidad a cierta hora del día.
¿Cómo se usará la base de datos y el DBSCAN?
El proyecto de Flickr cities cuenta con información de ciudades como París, Londres, Tokio, Buenos Aires o Torino. Para este ejercicio se utilizarán los datos de Torino por ser de un tamaño razonable comparado con ciudades más grandes y con mayor volumen de turistas.
Dado que el el algoritmo de DBSCAN se base en la densidad de datos principalmente, entendemos que en la ciudad existirán lugares con grandes cantidades de fotografías que denominaremos como lugares de interés general. Por ejemplo, pudiésemos encontrar monumentos históricos, museos, iglesias, estadios de fútbol, universidades, parques públicos entre otros.
Consideraremos como ruido a las fotograífas espontáneas que se toman en cualquier punto de la ciudad.
Básicamente, eliminando el “ruido” esperamos encontrar clústers identificados por el algoritmo cerca de lugares de interés general.
library(tidyverse)
library(dbscan)
torino <- read.csv("clean_points_torino_full.csv")
DT::datatable(head(torino[,2:7], 10), escape = FALSE,
caption = htmltools::tags$caption(style = 'caption-side: bottom; text-align: center;',
'Table: ', htmltools::em('Torino - Fotos')))
## Warning in instance$preRenderHook(instance): It seems your data is too big
## for client-side DataTables. You may consider server-side processing: https://
## rstudio.github.io/DT/server.html
Graficamos curva para determinar Eps
Con la gráfica de codo podemos determinar el valor del Eps (radio) optimo para cierta cantidad de puntos:
df_torino <- torino[2:3]
kNNdistplot(df_torino, k = 200)
abline(h=0.01, col = "red", lty=2)
Aplicamos DBSCAN y visualizamos los clústers obtenidos
Los parámetros definidos son:
eps = 0.01
minPts = 200
res <- dbscan(df_torino, eps = 0.01, minPts = 200)
res
## DBSCAN clustering for 29923 objects.
## Parameters: eps = 0.01, minPts = 200
## The clustering contains 9 cluster(s) and 3226 noise points.
##
## 0 1 2 3 4 5 6 7 8 9
## 3226 1001 23603 353 247 225 568 342 183 175
##
## Available fields: cluster, eps, minPts
Obtenemos la cantidad de clústers y la cantidad de puntos considerados como ruido (clúster 0).
Graficamos clústers
df_torino$cluster <- res$cluster
ggplot(df_torino, aes(x=longitude, y=latitude, colour=factor(df_torino$cluster))) +
geom_point()
## Warning: Use of `df_torino$cluster` is discouraged. Use `cluster` instead.
hullplot(df_torino[1:2], res)
## Warning in hullplot(df_torino[1:2], res): Not enough colors. Some colors will be
## reused.
Definimos la misma cantidad de grupos obtenidos con DBSCAN. k = 10
df_torino_KM <- torino[2:3]
df_torino_KM$cluster <- kmeans(df_torino_KM, centers=10, nstart=25)$cluster
ggplot(df_torino_KM, aes(x=longitude, y=latitude, colour=factor(cluster))) +
geom_point()
En éste caso, al armar los clústers con K-Means vemos todos los puntos (imagenes) forman parte de algún grupo, donde tambien se consideran las fotos espontáneas las cuales no corresponden a algún sitio de interés general.
df_centro <- df_torino %>%
filter(cluster == 2)
Graficamos curva para determinar Eps
kNNdistplot(df_centro[1:2], k = 100)
abline(h=0.0025, col = "blue", lty=2)
Aplicamos DBSCAN y visualizamos los clústers obtenidos
res <- dbscan(df_centro[1:2], eps = 0.0025, minPts = 100)
res
## DBSCAN clustering for 23603 objects.
## Parameters: eps = 0.0025, minPts = 100
## The clustering contains 13 cluster(s) and 2984 noise points.
##
## 0 1 2 3 4 5 6 7 8 9 10 11 12
## 2984 15550 602 655 114 1577 155 1063 157 134 141 260 110
## 13
## 101
##
## Available fields: cluster, eps, minPts
Graficamos clústers
df_centro$cluster <- res$cluster
ggplot(df_centro, aes(x=longitude, y=latitude, colour=factor(df_centro$cluster))) +
geom_point()
## Warning: Use of `df_centro$cluster` is discouraged. Use `cluster` instead.
hullplot(df_centro[1:2], res)
## Warning in hullplot(df_centro[1:2], res): Not enough colors. Some colors will be
## reused.
library(leaflet)
pchIcons = function(pch = 1, width = 30, height = 30, bg = "transparent", col = NULL, ...) {
n = length(pch)
files = character(n)
# create a sequence of png images
for (i in seq_len(n)) {
f = tempfile(fileext = '.png')
png(f, width = width, height = height, bg = bg)
par(mar = c(0, 0, 0, 0))
plot.new()
points(.5, .5, pch = pch[i], col = col[i], cex = min(width, height) / 8, ...)
dev.off()
files[i] = f
}
files
}
leaflet(df_centro)%>% addTiles() %>%
addMarkers(
data = df_centro,
icon = ~ icons(
iconUrl = pchIcons(pch= cluster,width=40,height=40,col=cluster,lwd=4),
popupAnchorX = 20, popupAnchorY = 0
))
(Para la presentación estamos utiliando una imagen del mapa obtenido. Si se habilita el código anterior puede desplegarse el mismo.)
Al eliminar el ruido podemos identificar los sitios de interes, los cuales pueden coincidir con: parques, estadios, estaciones de trenes, universidades, sitios turísticos, fábricas, etc.
Algunas de las aplicaciones de DBSCAN realizadas con exito son: la deteccion de usos en las tierras a partir de imagenes satelite, la creacion de perfiles de usuarios en Internet mediante la agrupacion de sesiones Web, o el agrupamiento de bases de datos de imagenes en histogramas en color facilitando la busqueda de imagenes similares
Detección del uso del terreno para distintos años:
Secciones de un embrión:
Imagenes satelitales:
Por ej. permite indentificar el porcentaje de concreto en una sección de la ciudad, así mismo también se puede realizar una aproximación sobre la cantidad de casas con techo de laminado o el porcentaje de calles pavimentadas, etc.
Clustering con diferentes algoritmos: